package tic_tac_toe_game;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Vector;

/**
 * author :  apurv verma
 * email  :  dapurv5@gmail.com
 */

public class GameEngine{
	
	public static int MAXDEPTH=Integer.MAX_VALUE; 
		
	/*
	 * TAKES INPUT FROM USER TO CREATE A MOVE AND RETURNS IT
	 */
	private Move createMove(){
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		Move m=new Move();
        int row = 0;
        int col = 0;
        try {
        	row = Integer.parseInt(in.readLine());
            System.out.print("row=" + row);
            col = Integer.parseInt(in.readLine());
            System.out.println("col=" + col);
        } catch (Exception e) { }
        m.row = row;
        m.column=col;
        return m;
	}
	
	/*
	 * MAKES THE MOVE m ON THE GIVEN GAME STATE g.
	 */
	private void makeMove(GameState g,int player,Move m){
		g.board[m.row][m.column]=player;
		g.count++;
	}
	
	/*
	 * ENUMERATES THE LIST OF POSSIBLE GAMESTATES FOR THE PLAYER player FROM THE CURRENT GAMESTATE AND RETURNS THEM AS AN ARRAY. 
	 */
	private GameState[] possibleMoves(GameState gs,int player){
		int k=0;
		GameState[] moves=new GameState[9-gs.count];
		try{
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(gs.board[i][j]==GameState.VACANT){
						GameState g=(GameState) gs.clone();
						g.board[i][j]=player;
						g.count++;
						moves[k]=g;
						k++;
					}
				}
			}
		}
		catch(Exception e){e.printStackTrace();}
		return moves;
	}
	
	/*
	 * GAME FUNCTION
	 */
	public void playGame(GameState gs){
		
		while(true){
			gs.printBoard();
			if(gs.hasBeenWon()){
				if(gs.humanHasWon()){
					System.out.println("Human has won");////
					break;
				}
				else if(gs.machineHasWon()){
					System.out.println("Machine has won");////
					break;
				}
			}
			if(gs.isDraw()){
				System.out.println("Draw");////
				break;
			}
			Move m=createMove();
			makeMove(gs,GameState.HUMAN,m);
			gs=alphaBeta(gs,GameState.MACHINE,0);
		}
	}
	
	
	/*
	 * EVALUATES THE CURRENT GAME STATE AND RETURNS A FLOAT VALUE.
	 * RETURNS MORE POSITIVE VALUE IF THE GAMESTATE IS MORE FAVOURABLE TO GameState.HUMAN
	 * RETURNS MORE NEGATIVE VALUE IF THE GAMESTATE IS MORE FAVOURABLE TO GameState.MACHINE
	 */
	public float gameStateEvaluation(GameState gs, int player) {
		 	
	        float base = 0.0f;
	        if (gs.humanHasWon())  {
	            return base + (1.0f)+(9-gs.count);
	        }
	        if (gs.machineHasWon())  {
	            return -(base + (1.0f)+(9-gs.count));
	        }
	        return base;
	    }

	/*
	 * RETURNS THE BEST POSSIBLE GAMESTATE FOR THE PLAYER player.
	 */
	public GameState alphaBeta(GameState gs,int player,int depth){
		
		if(reachedMaxDepth(gs,depth))
			return gs;
		
		float value=alphaBetaHelper(gs,player,depth,Float.MIN_VALUE,Float.MAX_VALUE);//FIND THE HEURISTIC VALUE OF THE BEST MOVE.
		GameState gnext=null;
		float v=0;
		GameState[] moves=possibleMoves(gs,player);
		for(int i=0;i<moves.length;i++){
			v=alphaBetaHelper(moves[i],GameState.otherPlayer(player),1,Float.MIN_VALUE,Float.MAX_VALUE);
			if(v==value){
				gnext=moves[i];													//MATCH WHICH GAME STATE CORRESPONDS TO THIS VALUE.
				break;
			}
		}
		if(moves.length==1)//IF THIS IS THE LAST GAMESTATE POSSIBLE.
			gnext=moves[0];
		return gnext;
	}

	
	
	private float alphaBetaHelper(GameState gs,int player,int depth,float alpha,float beta){
		
		if(reachedMaxDepth(gs,depth)){
			float value=gameStateEvaluation(gs,player);
			return value;
		}
		
		GameState[] moves=possibleMoves(gs,player);
				
		if(player==GameState.HUMAN){	//WE NEED TO FIND THE MOVE WITH THE MAX HEURISTIC VALUE. THAT IS THE BEST MOVE FOR HUMAN 
			for(int i=0;i<moves.length;i++){
				float value=alphaBetaHelper(moves[i],GameState.otherPlayer(player),depth+1,alpha,beta);
				if(value>alpha ){				
					alpha=value;
				}
				if(alpha>=beta)	{
					break;
				}
			}
			return  alpha; 	
		}
		
		if(player==GameState.MACHINE){	//WE NEED TO FIND THE MOVE WITH MINIMUM HEURISTIC VALUE. THAT IS THE BEST MOVE FOR MACHINE.
			for(int i=0;i<moves.length;i++){
				float value=alphaBetaHelper(moves[i],GameState.otherPlayer(player),depth+1,alpha,beta);
				if(value<beta ){				
						beta=value;
				}
				if(alpha>=beta)	{
					break;
				}
			}
			return  beta; 	
		}
		//DEAD CODE
		return 0.0f;
	}
	
	public boolean reachedMaxDepth(GameState g, int depth) {
		//HERE WE ARE EVALUATING TILL THE END OF THE GAME AND NOT UPTO A PARTICULAR DEPTH.
        boolean ret = false;
        if (g.hasBeenWon())  ret = true;
        else if (g.isDraw()) ret = true;
        else if(depth==MAXDEPTH) ret=true;
        return ret;
    }
	
	public static void main(String args[]){
		GameEngine e=new GameEngine();
		GameState gtest=new GameState(new int[][]{{0,0,0},{0,0,0},{0,0,0}});
		e.playGame(gtest);
	}

}
